Budget-Feasible Sybil-Proof Mechanisms for Crowdsensing

The rapid use of smartphones and devices leads to the development of crowdsensing (CS) systems where a large crowd of participants can take part in performing data collecting tasks in large-scale distributed networks. Participants/users in such systems are usually selfish and have private information, such as costs and identities. Budget- feasible mechanism design, as a subfield of auction theory, is a useful paradigm for crowdsensing, which naturally formulates the procurement scenario with buyers’ budgets being considered and allows the users to bid their private costs. Although the bidding behavior is well-regulated, budget-feasible mechanisms are still vulnerable to the Sybil attack where users may generate multiple fake identities to manipulate the system. Thus, it is vital to provide Sybil-proof budget-feasible mechanisms for crowdsensing. In this paper, we design a budget-feasible incentive mechanism which can guarantee truthfulness and deter Sybil attack. We prove that the proposed mechanism achieves individual rationality, truthfulness, budget feasibility, and Sybil-proofness. Extensive simulation results further validate the efficiency of the proposed mechanism.

Download paper here

Recommended citation: Liu, Xiang, et al. “Budget-Feasible Sybil-Proof Mechanisms for Crowdsensing.” International Workshop on Frontiers in Algorithmics. Cham: Springer International Publishing, 2022.